#使用快排对数组进行排序
import random


def quickSort(d,size,lf,rg):
    if lf < rg:     #排序数列的左边和右边
        lf_idx = lf + 1
        while d[lf_idx] < d[lf]:
            if lf_idx >= size:
                break
            lf_idx += 1
        rg_idx = rg
        while d[rg_idx] > d[lf]:
            rg_idx -= 1
        while lf_idx < rg_idx:
            d[lf_idx],d[rg_idx] = d[rg_idx],d[lf_idx]
            lf_idx += 1
            while d[lf_idx] < d[lf]:
                lf_idx += 1
            rg_idx -= 1
            while d[rg_idx] > d[lf]:
                rg_idx -= 1
        d[lf],d[rg_idx] = d[rg_idx],d[lf]
        #分割前后接着递归排序
        quickSort(d,size,lf,rg_idx - 1)
        quickSort(d,size,rg_idx + 1,rg)
#插值查找法
def interSearch(data,val):
    low = 0
    high = 49
    while low < high and val != -1:
        mid = low + int((val - data[low]) / (data[high] - data[low]) * (high - low))
        if val == data[mid]:
            return mid
        elif val < data[mid]:
            high = mid - 1
        elif val > data[mid]:
            low = mid + 1
    return -1

def main():
    val = 1
    data = [0] * 50
    for i in range(50):
        data[i] = random.randint(1,150)
    #为数组排序
    quickSort(data,len(data),0,len(data)-1)
    #数组内容
    for i in range(5):
        for j in range(10):
            print('%2d [%3d] '%(i*10+j+1,data[i*10+j]),end='')
        print()
    #二分法查找
    while True:
        num = 0
        val = int(input("请输入查找值(1-150),输入-1结束："))
        if val == -1:
            break
        num = interSearch(data,val)
        if num == -1:
            print("=============没有找到[%2d]============="%val)
        else:
            print('在第%2d的位置找到了%3d'%(num+1,data[num]))

if __name__ == '__main__':
    main()